//  最小堆
// 使用数组实现
class Heap {
    constructor() {
        // 一段连续的存储空间
        this.data = [];
        // 存储空间大小
        this.cnt = 0;
    }
    // push
    push(x) {
        // 记录添加之后的最后一个元素的下标
        let ind = this.cnt;
        // 数组尾部添加
        this.data[this.cnt++] = x;
        // 从底部向上进行调整
        // 节点ind的父节点为(ind-1)>>1
        // 上浮
        while (ind && this.data[(ind - 1) >> 1] > this.data[ind]) {
            this.swap(ind, (ind - 1) >> 1);
            ind = (ind - 1) >> 1;
        }
    }
    // pop
    pop() {
        // 保存堆顶元素
        let top = this.top();
        // 将树底部最后一个元素移动到堆顶位置
        this.data[0] = this.data[--this.cnt];
        // 重置数组长度
        this.data.length = this.cnt;
        let n = this.cnt,
            ind = 0,
            tmp = ind;
        // 存在子节点情况下
        // 下沉
        while (ind * 2 + 1 <= n) {
            // 父节点值大于左子节点值，交换这两个节点，tmp保存的是小值的下标
            if (this.data[ind] > this.data[ind * 2 + 1]) tmp = ind * 2 + 1;
            // 存在右子节点情况下，右子节点较小，则与tmp进行交换
            if (ind * 2 + 2 <= n && this.data[tmp] > this.data[ind * 2 + 2])
                tmp = ind * 2 + 2;
            // 交换后tmp与ind相同，则符合父节点小于子节点规则，不需要交换
            if (ind == tmp) break;
            this.swap(ind, tmp);
            // ind重新赋值，继续下沉
            ind = tmp;
        }
        return top;
    }
    size() {
        return this.cnt;
    }
    // 交换数组中两个元素的位置
    swap(a, b) {
        [this.data[a], this.data[b]] = [this.data[b], this.data[a]];
    }
    top() {
        return this.data[0];
    }
}
let arr = [8, 6, 9, 4, 5, 0, 1, 3, 2, 7];
function heap_sort(arr) {
    let h = new Heap();
    arr.forEach((v) => h.push(v));
    let ret = [];
    while (h.size()) ret.push(h.pop());
    arr.length = 0;
    arr.push(...ret);
}
heap_sort(arr);
console.log(arr);
